Definition

An oracle machine be visualized as Turing machine with a black box (oracle), able to solve a certain kind of problem in a single operation.

Notes

  • useful to study how certain operation complexities depend on other ones (without necessarily defining that operation's complexity)
  • formalization: oracle Turing machine (which similarly allows non-deterministic oracle TM to be defined)

References:

  1. https://en.wikipedia.org/wiki/Oracle_machine
  2. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, pp. 73-74.